package com.leetcode.search;

import java.util.*;

/**
 * leetcode 210 课程表
 */
public class Solution210 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if (numCourses == 0 || prerequisites == null) {
            return new int[0];
        }
        // 构造前置条件
        Map<Integer, ArrayList<Integer>> preCondition = new HashMap<>();
        for (int i = 0; i < prerequisites.length; i++) {
            if (!preCondition.containsKey(prerequisites[i][0])) {
                preCondition.put(prerequisites[i][0],
                        new ArrayList<>(Arrays.asList(prerequisites[i][1])));
            } else {
                preCondition.get(prerequisites[i][0]).add(prerequisites[i][1]);
            }
        }
        // 构造后置条件
        Map<Integer, ArrayList<Integer>> postCondition = new HashMap<>();
        for (int i = 0; i < prerequisites.length; i++) {
            if (!postCondition.containsKey(prerequisites[i][1])) {
                postCondition.put(prerequisites[i][1],
                        new ArrayList<>(Arrays.asList(prerequisites[i][0])));
            } else {
                postCondition.get(prerequisites[i][1]).add(prerequisites[i][0]);
            }
        }

        boolean[] studied = new boolean[numCourses];
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            if (preStudied(preCondition.get(i), studied) && !studied[i]) {
                if (isFind(i, preCondition, postCondition, studied, result)) {
                    return result.stream().mapToInt(Integer::intValue).toArray();
                }
            }
        }

        return new int[0];
    }

    private boolean isFind(Integer course, Map<Integer, ArrayList<Integer>> preCondition,
                           Map<Integer, ArrayList<Integer>> postCondition,
                           boolean[] studied, List<Integer> result) {
        studied[course] = true;
        result.add(course);
        if (result.size() == studied.length) {
            return true;
        }
        // 没有后置课程
        if (postCondition.get(course) == null) {
            return false;
        }


        // 学后置课程
        for (Integer postCourse : postCondition.get(course)) {
            if (preStudied(preCondition.get(postCourse), studied) && !studied[postCourse]) {
                if (isFind(postCourse, preCondition, postCondition, studied, result)) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean preStudied(List<Integer> preConditions, boolean[] studied) {
        if (preConditions == null) {
            return true;
        }
        return preConditions.stream().allMatch(preCondition -> studied[preCondition] == true);
    }

    public static void main(String[] args) {
        Solution210 solution210 = new Solution210();
        System.out.println(solution210.findOrder(4,
                new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}}));
    }
}
